package my.jwds.lcs02;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

/**
 * LCS 02. 完成一半题目<br/>
 * <a href="https://leetcode-cn.com/problems/WqXACV/">完成一半题目</a>
 */
public class HalfQuestions {


    public static void main(String[] args) {
        int a1[] = {1,5,1,3,4,5,2,5,3,3,8,6};
        System.out.println(new HalfQuestions().halfQuestions(a1));
    }


    public int halfQuestions(int[] questions){
        HashMap<Integer,Integer> questionsMap = new HashMap<>();
        for (int question : questions) {
            Integer temp =questionsMap.get(question);
            if (temp == null)temp=0;
            questionsMap.put(question,++temp);
        }
        int person = questions.length / 2;
        ArrayList<Integer> count = new ArrayList<>(questionsMap.values());
        if (count.size() == questions.length) return person;
        if (Collections.max(count) > person)return 1;
        Collections.sort(count);
        for (int i = count.size() -1; i >=0; i--) {
            if ((person = person - count.get(i)) <= 0){
                return count.size() - i;
            }
        }
        return questions.length / 2;
    }
}
